HW#2 --- last modified February 07 2019 04:44:22..

Solution set.

Due date: Mar 15

Files to be submitted:
  Hw2.zip

Purpose:

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO3 -- Describe a language in terms of a regular expression.

LO4 -- Find a regular expression for a language described by a finite automaton and conversely.

LO5 -- Construct a deterministic finite automaton from a non-deterministic one.

LO6 -- Minimize a deterministic automaton.

LO7 -- Be able to use a pumping lemma to show that some languages are not regular and/or not context-free. Use closure properties to simplify proofs of non-regularity of languages.

Specification:

Group 1 (Must be handwritten, due start of class Feb. 27).

1. Let `L = {w | mbox{w begins with three 1's}}` and `L' = {w | mbox{w begins with two 0's}}`. Draw NFA's for both languages. Then use the constructions from class to make NFA's for `LL'`, `L cup L'`, and `L^\star`.
2. Use the power set construction to convert your NFA from the last exercise for `L cup L'` into a DFA then do state minimization on the result.
3. Use the construction from class or the book to step-by-step convert your DFA from the last exercise to a regular expression.
4. Using the construction from class give a right-linear grammar for the DFA you obtained above.

Group 2 (Must be handwritten, due start of class Mar. 6).

1. Let `L = {w in {a,b,..z, 0,1}^\star | w mbox( has an odd number of 1's)}`. Let `L' = {v in {a, o, n, e}^\star | mbox(the word "one" appears in v an odd number of times and the letter e only appears in one's)}`. Give a homomorphism `h` from the language of `L` to that of `L'`. Next make a regular expression for `L'` by using the construction from class to obtain a regular expression for `h(L)`.
2. Let `A={fished, fish, fishes, fish\i\n\g, jump\i\n\g, o\r\a\n\g\e\s}` and `B={i\n\g, ed}`. Give DFAs for each of these languages. Then using Ginsberg and Spanier's construction give an automata for `frac{A}{B}`.
3. Let `L` be the language consisting of strings `w = xyz` over the alphabet `{a,b,c}` where `|x| = |z|` and `y` uses only symbols not in `x` or `z`. Show using the pumping lemma this language is not regular.
4. For a language `L` over `{0,1}` let `\O\n\e_L = {1w| w in L}`. For each of the languages `L` of Exercise 2.4 from the book, give the CFG for `\O\n\e_L`.

Group 3 (Must be handwritten, due start of class Mar. 13).

1. Give an example CFG which has useless productions, a nullable variable, and a unit production. For this grammar show the result of applying the algorithm from class for each of eliminating these.
2. Consider the grammar `S -> 0|0S0 | 1S0 |0S1`. Use the algorithm from class to step-by-step convert this grammar to Chomsky Normal Form.
3. Show step-by-step the result of applying the CYK algorithm to the grammar of the previous problem on the following strings: `00011` andd `11`.
4. Convert the grammar `S -> 0|0S0 | 1S0 |0S1` to Greibach Normal Form.

For the coding part of this assignment I would like you to implement the CYK algorithm in Java. In your Hw2.zip file I would like you to have your source code (not class files). Your program will be compiled by unzipping Hw2.zip, switching into the resulting directory, and executing the command:

javac Cyk.java

To run your program, I will type commands like:

java Cyk grammar_file some_string

Here grammar_file will be the name of some text file containing a context free grammar. We will assume the alphabet of all grammars is `{a, b}`, the precise format of the grammar will be describe below. Here some_string is a string over `a`,`b`. On such an input, your program should either print true or print false depending on whether some_string can be generated by the grammar in the file. It should then stop. Your program should not output anything else and should operate almost instantaneously and correctly on the test cases given to receive the points for the test cases indicated below.

The grammar file should consist of a sequence of lines of the form:

`(0 cup 1)^+:(0 cup 1)^+,(0 cup 1)^+`

or of the form:

`(0 cup 1)^+:(a cup b)`

You should implement a DFA to recognize whether a line is valid. An example file might be:

0:1,10
1:a
10:b

The intended meaning of this grammar is `A_0 -> A_1 A_(10)`, `A_1 -> a`, `A_(10) -> b`. The left-hand variable of the first line in a file is the start variable. So in this case `A_0`. This completes the description of a grammar file. Suppose the file grammar.txt contained the above lines. Here is some examples of what it should look like running your program from a Unix command line prompt:

#java Cyk grammar.txt ab
true
#java Cyk grammar.txt bbb
false

Point Breakdown